Color refinement is a classical technique used to show that two given graphsG and H are non-isomorphic; it is very efficient, although it does not succeedon all graphs. We call a graph G amenable to color refinement if it succeeds indistinguishing G from any non-isomorphic graph H. Tinhofer (1991) explored alinear programming approach to Graph Isomorphism and defined compact graphs: Agraph is compact if its fractional automorphisms polytope is integral. Tinhofernoted that isomorphism testing for compact graphs can be done quite efficientlyby linear programming. However, the problem of characterizing and recognizingcompact graphs in polynomial time remains an open question. Our results are summarized below: - We show that amenable graphs are recognizable in time O((n + m)logn), wheren and m denote the number of vertices and the number of edges in the inputgraph. - We show that all amenable graphs are compact. - We study related combinatorial and algebraic graph properties introduced byTinhofer and Godsil. The corresponding classes of graphs form a hierarchy andwe prove that recognizing each of these graph classes is P-hard. In particular,this gives a first complexity lower bound for recognizing compact graphs.
展开▼
